<HTML> <TITLE>Work:

Compression Practicum </TITLE> <BODY> <CENTER><H1>Work:

Compression Practicum </H1></CENTER> <CENTER><H3>Jeffreys
Copeland &amp; Haemer</H3></CENTER>
<CENTER><H3>(<I>Server/Workstation Expert</I>, April
2001)</H3></CENTER>
<BR> <P> <BR><BLOCKQUOTE><I> In general, the later chapters
contain more reliable information than the earlier ones do.  The
author feels that this technique of deliberate lying will
actually make it easier for you to learn the ideas.  </I><BR>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ---  Donald E Knuth,
<I>The TeXbook</I> </BLOCKQUOTE> <P> <BR><BLOCKQUOTE><I> Outside
of a dog, a book is a man's best friend.  Inside of a dog, it's
too dark to read.  </I><BR>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ---  Groucho Marx
</BLOCKQUOTE> <P>
<BR> <P> As part of our first column this year -- ``Reader
Filters,'' in the January issue of this magazine (or locally at
<TT><A
HREF="http:palm.html">http:palm.html</A></TT>)
-- we wrote a Perl script to convert text into a form readable on
the popular Palm handheld computer, by applications such as Bill
Clagett's CSpotRun, <TT><A
HREF="http://32768.com/cspotrun/">http://32768.com/cspotrun/</A></TT>.
<BR> <P> One of the features we didn't develop in
<TT>txt2palm</TT> was compression.  And, since we discussed
compression in last month's column, it seemed a good time to
revisit the topic.  We tossed off an explanation of the Palm
compression scheme, and told you, ``Given that information you
should be able to produce some Perl code to replace the short
placeholder,'' with the implication that the code for the
compression would be simple.  And once the January issue hit the
streets, we had a note from Gary Sabot, a finance wonk who is
getting tired of moving data from his Sun to his PC in order to
convert it for his Palm.  Gary asked specifically about the
compression code.
<BR> <P> Unfortunately, we lied to you.  It wasn't a completely
deliberate lie, because we hadn't fully thought the problem
through.  Even though the Palm compression scheme is fairly
simple, and Perl provides wonderful regular expression and string
processing features, writing the necessary code in Perl would
have been a bit difficult.  So, in the Knuth mold, this later
chapter contains more reliable information that the earlier one.
<BR> <P>
<BR> <P><P><BR> <FONT SIZE=+1><I>Palm DOC
Compression.</I></FONT><BR> Typically, the compression scheme for
Palm documents results in reducing text to roughly 55% of its
original size.  Not as good as some of the tools we explored last
month but still pretty good.  How does it do that?  Well, let's
review.  There are four classes of characters in a compressed
Palm DOC file.  <UL> <LI> Characters that represent themselves,
which are just copied from the compressed buffer to the output.
This set consists of the ASCII characters from tab
<TT></TT>(<TT>0x09</TT>) through DEL <TT></TT>(<TT>0x7F</TT>),
and NUL <TT></TT>(<TT>0x00</TT>).  <LI> A single-byte
compression.  A space followed by a character from <TT>0x40</TT>
through <TT>0x7F</TT> is compressed into a single character by
setting the high bit.  Thus two bytes, a space followed by J, can
be compressed into a single byte of <TT>0xCA</TT>.  <LI>
Characters that introduce a literal block.  The characters from
<TT>0x01</TT> through <TT>0x08</TT> introduce a block of that
many characters that are copied literally from the compressed
buffer.  This allows characters that are special codes to appear
in the output, which means that upper range Latin 1 characters
(like &Euml;, which is also encoded as <TT>0xCA</TT>) won't be
confused with the space-compressed characters from the previous
class.  <LI> Run-length encoding.  A run of characters that
appears previously in the file can be encoded as two bytes.  If
we see a repeatable sequence between three and ten bytes, no more
than 2047 bytes previously, we subtract three from the length of
the sequence, and pack it and the distance into two bytes:
<BLOCKQUOTE><PRE>
0x8000 + (distance &lt;&lt; 3) + ((length-3) &amp; 0x07)
</PRE></BLOCKQUOTE>
This allows us to store a sequence of up to ten bytes in two.
There's a clear tradeoff here: we could make a scheme to store
longer sequences but our maximum horizon for finding them would
have to be shorter.  </UL> It's this last class of compressed
characters that's a bit difficult to implement in Perl.  However,
that's just fine, because it allows us a chance to show you how
to link a C language routine into a Perl package.
<BR> <P>
<BR> <P><P><BR> <FONT SIZE=+1><I>Perl Packages with
C.</I></FONT><BR> You might be surprised to realize that we can
build Perl packages in C, but it's not quite as complicated as it
might seem.  In essence we will be inverting the steps you take
when you install a package from the Comprehensive Perl Archive
Network, CPAN.
<BR> <P> We begin to build our compression package by generating
a template with
<BLOCKQUOTE><PRE>
h2xs -A -n PalmComp
</PRE></BLOCKQUOTE>
This creates a directory <TT>PalmComp/</TT> containing a
<TT>Makefile</TT> generator, <TT>Makefile.PL</TT>, a module file
for the package, <TT>PalmComp.pm</TT>, an extension module,
<TT>PalmComp.xs</TT>, and a test template, <TT>test.pl</TT>.  We
will ignore the test template for the moment, because we'll add
some test code directly to the package.  Our first step will be
to add RCS id strings in the templates, and then in
<TT>PalmComp.pm</TT> we'll add the name of the routine we want to
publicly expose into the exports list, and flesh out the POD
(Plain Old Documentation) in-line manual page.
<BLOCKQUOTE><PRE>
# $ID: PalmComp.pm,v 1.2 ...
package PalmComp;

use strict;
use vars qw($VERSION @ISA @EXPORT @EXPORT_OK);

require Exporter;
require DynaLoader;
require AutoLoader;

@ISA = qw(Exporter AutoLoader DynaLoader);
# Items to export into callers namespace
#   by default.
@EXPORT = qw(compress);
$VERSION = '0.95';

bootstrap PalmComp $VERSION;

1;
__END__

=head1 NAME

PalmComp - Perl extension for
Palm PDB compression

=head1 SYNOPSIS

  use PalmComp;
  compress(buffer, length);

=head1 DESCRIPTION

This module compresses a buffer for a Palm PDB
file, as described in our April, 2001 "Work"
column.

=head1 AUTHOR

Jeffrey Copeland C&lt;copeland@alumni.caltech.edu&gt;

Jeffrey S Haemer C&lt;jsh@usenix.org&gt;

=head1 SEE ALSO

perl(1).

=cut
</PRE></BLOCKQUOTE>
<BR> <P> Next, we need to flesh out the <TT>PalmComp.xs</TT>
template with appropriate C code.  We can retain a simple
skeleton, for the moment:
<BLOCKQUOTE><PRE>
#include "EXTERN.h"
#include "perl.h"
#include "XSUB.h"

/* $ID: PalmComp.xs,v 1.2 ... */
#define REAL_MODULE
#include "comp.c"

MODULE = PalmComp        PACKAGE = PalmComp

void
compress( buf, length )
 char *buf;
 int length;
PREINIT:
 int len;
PPCODE:
 len = compress(buf,length);
 EXTEND(SP,2);
 PUSHs(sv_2mortal(newSVpvn(buf,len)));
 PUSHs(sv_2mortal(newSViv(len)));
</PRE></BLOCKQUOTE>
<BR> <P> The first three include files were provided by
<TT>h2xs</TT>, but we've added the include of <TT>comp.c</TT> and
definition of <TT>REAL_MODULE</TT>, both of which we'll explain
in a little bit.  The body of the routine is interpreted by
<TT>xsubpp</TT>, which generates raw C code from the <TT>XS</TT>
file.  The simplest possible <TT>XS</TT> code would be something
like
<BLOCKQUOTE><PRE>
void
hello()
CODE:
 printf("hello, world\n");
</PRE></BLOCKQUOTE>
<BR> <P> We've used a slightly more complicated set of tags.
<TT>PREINIT</TT> gives us the ability to declare local variables
without fear of interference from the code <TT>xsubpp</TT>
generates.  Because we want to return two values, the Perl call
will be something like
<BLOCKQUOTE><PRE>
($newbuf, $newlen) = compress($buf,$len);
</PRE></BLOCKQUOTE>
and we use the <TT>PPCODE</TT> keyword.  This introduces code
that won't have return values automatically put on the stack.  We
put those values there ourselves by extending the stack with
<TT>EXTEND</TT>, and pushing the return values with
<TT>PUSH</TT>.  The other important calls here are
<TT>sv_2mortal</TT>, which instantiates a stack version of a
variable that won't be accidentally cleaned up by Perl's garbage
collector, and <TT>newSViv</TT> and <TT>newSVpvn</TT>, which
generate new stack values from an integer and a pointer/length
pair, respectively.
<BR> <P> You'll notice that we've still avoided talking about the
actual compression routine.  Our <TT>XS</TT> routine called
<TT>compress</TT> calls another routine called <TT>compress</TT>,
which is (presumably) included from a file <TT>comp.c</TT>.  How
can <TT>compress</TT> call <TT>compress</TT>?  It's not a
recursive call because <TT>xsubpp</TT> converts the ``Perl glue''
name below the <TT>MODULE</TT> declaration in the <TT>XS</TT>
file using something like C++'s name mangling.
<BR> <P> Once we've got the module ready, we can generate a
makefile to build and install it with <TT>perl Makefile.PL</TT>.
<BR> <P> (Yes, we're covering this quickly and loosely.  We
recommend you read the <I>perlXStut</I> and <I>perlXS</I> man
pages for details.)
<BR> <P>
<BR> <P><P><BR> <FONT SIZE=+1><I>The Real Compression
Routine.</I></FONT><BR> You've been patient enough with the
wrapper.  We now get to the contents of the <TT>comp.c</TT> file:
<BR> <P>
<BLOCKQUOTE><PRE>
static char *id = "$ID: comp.c,v 1.6 ... ";
#include &lt;stdlib.h&gt;
#include &lt;stdio.h&gt;
#include &lt;string.h&gt;

int nextmatch(
  unsigned char *, int, int *);
void populate_runs(
  unsigned char *, int *, int);
int memchk(
  unsigned char *, unsigned char *);
</PRE></BLOCKQUOTE>
We begin with our usual debris for a C program, an RCS id line,
some include files, and prototypes.  Notice that because we're
going to be doing a lot of character comparisons, we're using
unsigned characters.
<BR> <P>
<BLOCKQUOTE><PRE>
#define HAVECHARS ((p+1) &lt; (buf+len))
#define COUNTABLE(x)  \
  ((((x)&gt;=1 &amp;&amp; (x)&lt;=8)) || ((x)&gt;=0x80))
</PRE></BLOCKQUOTE>
These two macros will prove useful.  The first will be true if we
have characters left in the buffer.  The second will be true if
we are looking at a character which needs to be preceeded by a
count.
<BR> <P>
<BLOCKQUOTE><PRE>
int
compress(unsigned char *buf, int len)
{
 unsigned char *new, *p, *np, *t;
 int *runs, rr;
</PRE></BLOCKQUOTE>
The actual compression routine begins fairly routinely, for lack
of a better word.  We expect the buffer and its length, which we
passed from our <TT>txt2palm</TT> program to the Perl glue
version of <TT>compress()</TT> in the <TT>XS</TT> file, and
thence here.  Our only function return value is the length; we'll
replace the original buffer with the compressed buffer as part of
our return.  We also declare a flock of variables, which will be
explained in due course.  (A narrative disadvantage of C compared
to C++ and Perl is that we can only declare variables at the top
of a block, and so have to tell you all their names before we're
ready to explain what they do.  It's a reason we occasionally
like writing in CWEB.)
<BR> <P> The creation of the buffer we'll be compressing into is
perhaps a bit tricky.  Last month we discussed cases where
compression is counterproductive, so we can envision
circumstances where we don't really compress the input.  So we
insure against that by allocating twice the memory of the
existing buffer.  If we can't allocate the memory, we return a
length of zero indicating a problem in the compression.
<BLOCKQUOTE><PRE>
 new = malloc(len*2);
 if( new == NULL )
  return 0;
</PRE></BLOCKQUOTE>
<BR> <P> The most complicated part of the process is finding the
runs of characters that we can express as compressed run lengths
-- those two-byte codes we talked about earlier.  We need to find
these ahead of any compression pass, because on the decompression
pass, the buffer preceeding the run length code will already be
uncompressed.  This means that the run count and distance needs
to be expressed in terms of the uncompressed buffer.
<BLOCKQUOTE><PRE>
 /* find forward references */
 runs = malloc(len * sizeof(int));
 if( runs == NULL )
  return 0;
 populate_runs(buf, runs, len);
</PRE></BLOCKQUOTE>
We rely on a routine called <TT>populate_runs</TT> to find them,
saving them in an array we dynamically allocate for the purpose.
Again, we return with an error if we have problems allocating the
array.  What happens in that first pass through the uncompressed
buffer?  Patience, please.  We'll get there.
<BR> <P> Once we've gathered information about the contents of
the buffer, we're ready to make the actual compression pass.
<BLOCKQUOTE><PRE>
 /* now we run through the text, and
 do the actual compression */
 for( p = buf, np = new;
  p &lt; (buf+len);  )
 {
</PRE></BLOCKQUOTE>
Our <TT>for</TT> loop is the obvious one: initialize our pointers
into the input and output buffers to their beginnings, and
continue until we reach the end of the input buffer.
<BLOCKQUOTE><PRE>
  /* if we've got a backreference, use it */
  if( (rr=runs[p-buf]) != 0 ) {
   *np++ = 0x80 | ((rr &gt;&gt; 8) &amp; 0x3F);
   *np++ = (rr &amp; 0xFF);
   p += (rr &amp; 0x07) + 3;
   continue;
  }
</PRE></BLOCKQUOTE>
<BR> <P> Our first step is easy.  If we've got an entry in the
<TT>runs</TT> array, we have a valid backreference, which we can
turn into a two-byte code.  Skip over the number of bytes this
new code represents, and continue with the next iteration of the
loop.
<BLOCKQUOTE><PRE>
  /* special case for character we need
   to escape: 1-&gt;8 &amp; 0x80-&gt;0xFF */
  if( COUNTABLE(*p) )
  {
   char *bp = np++;
   *bp = 1;
   *np++ = *p++;
   while( COUNTABLE(*p)
    &amp;&amp;  *bp &lt; 8  &amp;&amp;  HAVECHARS )
   {
    (*bp)++;
    *np++ = *p++;
   }
   continue;
  }
</PRE></BLOCKQUOTE>
Failing a simple run-length compression, we may have characters
that need to be escaped because they're in a range that
represents one of the special codes.  These are characters for
which the <TT>COUNTABLE</TT> macro is true.  We save a place for
the count, then walk over up to eight of them at a time,
backfilling the count as we go.
<BR> <P> In the next clause, we compress a space when we can.
<BLOCKQUOTE><PRE>
  /* compress a leading space */
  if( *p == ' '  &amp;&amp;
   HAVECHARS  &amp;&amp;
   runs[p+1-buf] == 0  &amp;&amp;
   p[1] &gt;= 0x40  &amp;&amp; p[1] &lt;= 0x7F )
  {
   *np++ = *(++p) | 0x80;
   p++;
   continue;
  }
</PRE></BLOCKQUOTE>
Notice that we're also checking that there's no run of characters
beginning right after this particular space character.  If there
is, it will provide better compression than the collapsed space,
since the minimum run length is three.
<BR> <P>
<BLOCKQUOTE><PRE>
  *np++ = *p++;
 }
</PRE></BLOCKQUOTE>
We close the <TT>for</TT> loop by copying any other character
from the input buffer to the output buffer without change.
<BR> <P>
<BLOCKQUOTE><PRE>
 *np = 0;
 if( np-new &gt; len )
  return 0;

 memcpy(buf, new, np-new);
 free(new);
 free(runs);
 return np-new;
}
</PRE></BLOCKQUOTE>
We're now done.  We return a zero for error if we didn't succeed
in making the buffer smaller.  Why?  Because the PDB file format
has a maximum of a 4096 byte buffer.  Typically, that's the size
of the uncompressed buffer we'll be handed.  If we haven't
managed to make it smaller, we will cause buffer size trouble for
a program on the Palm device itself.  In the normal case, though,
we copy the compressed buffer over the old one, and return the
length.
<BR> <P> This still leaves us with the question about collecting
character runs, which we will now answer:
<BLOCKQUOTE><PRE>
void
populate_runs(unsigned char *buf,
  int *runs, int len)
{
 int i, d, l;

 memset(runs, 0, len*sizeof(int));
</PRE></BLOCKQUOTE>
We begin in the usual way, making sure to set the freshly-allocated <TT>runs</TT> array to zeroes.
<BR> <P>
<BLOCKQUOTE><PRE>
 for( i = 0;  i &lt; (len-6);  i++ )
 {
  d = nextmatch(buf+i, len-i, &amp;l);
  if( d &gt; 0 )
   runs[d+i] = (d &lt;&lt; 3) | (l - 3);
 }
}
</PRE></BLOCKQUOTE>
The body of the routine is pretty simple, too, since we've put
the hard part off to <TT>nextmatch.</TT> When we find a run, we
save the information about it in the same form in which it will
be encoded in the compressed buffer -- length shifted left by
three bits, <TT>OR</TT>'ed with the length of the run minus
three.
<BR> <P> So the problem now boils down to finding the next match
of a character sequence in the input buffer.  Given a starting
point in the buffer, we want to find how far it is to the same
set of between three and ten characters.
<BLOCKQUOTE><PRE>
int
nextmatch(unsigned char *from,
    int buflen, int *matchlen)
{
 unsigned char *to;
 size_t n;
 size_t max;

 buflen = (buflen &gt; 2047) ?
  2047 : buflen;
</PRE></BLOCKQUOTE>
Because we only have 11 bits to store the maximum distance to the
matching string is 2047.  If we're closer than that to the end of
the buffer, we'll use the shorter distance.
<BLOCKQUOTE><PRE>
 for( to = from+1;
  to &lt; (from+buflen); to++ )
 {
  n = 3;
  max = (buflen &lt;= 10) ? buflen : 10;
  if( memcmp(from,to,n) != 0 ) continue;
  while( n &lt;= max  &amp;&amp;
   memcmp(from,to,n) == 0 )
     n++;
  *matchlen = (int) --n;
  return(to - from);
 }
 return 0;
}
</PRE></BLOCKQUOTE>
Our main loop does a long search, returning the distance to the
next forward match, and storing the length of the match in the
address passed as <TT>l</TT>.  If we fall through the bottom of
the loop, we return zero.  This is a completely brute force loop.
We haven't done any tuning on it at all.  How could we improve
this routine?  If we find a match close-by, should we pass it up
for a possibly longer match a bit farther up in the buffer?  What
changes would we need to make to the calling <TT>compress</TT>
routine to ensure that runs of Latin-1 characters will be used,
and that countable strings of characters won't be used instead.
We don't think that using one of the more efficient string search
algorithms, like Boyer-Moore, is much help in this circumstance
where we're mostly searching for short strings, but we haven't
done the analysis to prove it.
<BR> <P> We finish <TT>comp.c</TT> with a set of testing code.
We don't have space to show it to you, but you can find it on our
web site.
<BLOCKQUOTE><PRE>
#ifndef REAL_MODULE
/* this portion is for
  stand-alone testing only */
main( int ac, char *av[] )
{
 ...
}
#endif
</PRE></BLOCKQUOTE>
Notice that the test code compiles only if we have <I>not</I>
defined <TT>REAL_MODULE</TT>.  This allows us to compile without
the testing functionality by including <TT>comp.c</TT> after a
<TT>#define REAL_MODULE</TT>, as we do in the <TT>XS</TT> file.
<BR> <P>
<BR> <P><P><BR> <FONT SIZE=+1><I>Using The New
Function.</I></FONT><BR> Now that we are capable of doing
compression, we'll need to make some minor changes to the
<TT>txt2palm</TT> script we wrote for January.  We'll show these
as the output of <TT>diff -u2</TT> and run through them briefly.
<BR> <P>
<BLOCKQUOTE><PRE>
@@ -4,4 +4,5 @@
 use strict;
 use Getopt::Std;
+use PalmComp;

 ## useful constants
</PRE></BLOCKQUOTE>
Obviously, we need to include the new module.
<BR> <P>
<BLOCKQUOTE><PRE>
@@ -15,10 +16,7 @@

 ## command line flags
-use vars qw($opt_c);
-getopts("c")  ||
-    die "Usage: $0 [-c] title...\n";
-die "compression not supported yet\n"
-    if( $opt_c );
-
+use vars qw($opt_c $opt_v);
+getopts("cv")  ||
+    die "Usage: $0 [-cv] title...\n";
</PRE></BLOCKQUOTE>
We also add a <TT>-v</TT> flag to report on the compression we
achieved.  We change the usage messages to match the new
functionality.
<BR> <P>
<BLOCKQUOTE><PRE>
@@ -34,4 +32,5 @@
 my $text = &lt;STDIN&gt;;
 my $filesize = length($text);
+my $compsize = 0;

 ## We have a number of steps to do to
</PRE></BLOCKQUOTE>
We add a place to sum the compressed file size.
<BLOCKQUOTE><PRE>
@@ -55,5 +54,10 @@
     $pos += $RECMAX) {
 my $rec = substr($text,$pos,$RECMAX);
-    $rec = compress($rec) if($opt_c);
+    my $len = length($rec);
+    ($rec,$len) = compress($rec,$len)
+        if($opt_c);
+    die "Ooops:  unable to compress\n"
+             if($opt_c &amp;&amp; ! $len);
+    $compsize += $len;
 push(@records, $rec);
 }
</PRE></BLOCKQUOTE>
We use the new calling sequence for <TT>compress</TT>, as we've
discussed, throwing a fatal error if we had a compression
failure.  We also sum the compressed size of the data into
<TT>$compsize</TT>.
<BR> <P>
<BLOCKQUOTE><PRE>
@@ -147,8 +151,7 @@
 print @records;

-########################################
-
-# we don't provide a real compression
-# routine yet....
-
-sub compress() { $_[0] }
+    # print status if -v
+warn "$filesize compressed to $compsize, ",
+    "compression ratio = ",
+    int($compsize*100/$filesize), "%\n"
+    if( $opt_c &amp;&amp; $opt_v );
</PRE></BLOCKQUOTE>
Lastly, we can remove the stub compression routine, and finish
off the program with a report on our compression ratio, if the
user requested the information.
<BR> <P> To install and run this new software, you do the same
thing you would with any Perl package downloaded from the net:
<BLOCKQUOTE><PRE>
perl Makefile.PL
make install
</PRE></BLOCKQUOTE>
This will install the package in your designated place for Perl
modules.  At this point, you can do things like:
<BLOCKQUOTE><PRE>
txt2palm -cv "list of work columns" &lt;work.txt &gt;work.pdb
</PRE></BLOCKQUOTE>
<BR> <P> There you have it.  An implementation of a simple
compression scheme we've discussed before, some new tricks for
Perl packages, and some added functionality to code we showed you
before.  Not bad for our month's amusement.  Some time in the
future, we'll show you a way to generate test data for text
processing programs such as these, but next time, we'll be back
with a discussion of how to organize the epigrammic wisdom of the
ages.
<BR> <P> Lastly, it's with sadness that we note the death on
February 7th, as we were working on this column, of Dale Evans
Rogers, who wrote the cowboy standard from which we take our
signoff.  As usual, we wish you, and especially Dale, happy
trails.
<BR> <P>
<BR> <P><P><BR> <FONT SIZE=+1><I>Note added to the
proofs:</I></FONT><BR> In the month between writing and proofing
this article, we've improved the compression of our
<TT>PalmComp</TT> module in some of the ways suggested in the
main text.  The improved version (which includes tests in Perl)
is bundled with the original at our web sites.
<BR> <P> Also in the intervening month, two interesting bits of
data have come our way.  First, John Gruenenfelder has developed
a better compression algorithm for documents to be read on the
Palm.  He intended it for reading larger works, such as the free
books from Project Gutenberg, <TT><A
HREF="http://promo.net/pg">http://promo.net/pg</A></TT>.
Because the compression scheme is incompatible, it requires new
conversion tools and a new reader, called GutenPalm.  They're
available at <TT><A
HREF="http://gutenpalm.sourceforge.net">http://gutenpalm.sourceforge.net</A></TT>.  Second, a
company named Agenda Computing is working on a Linux-based hand-held device, the Agenda VR3.  See their web site, <TT><A
HREF="http://www.agendacomputing.com/">http://www.agendacomputing.com/</A></TT>, for details.
It looks like vaporware as we write, but it's clearly got some
possibilities.
<BR> <P>
<BR> <P><P><BR> <FONT SIZE=+1><I>Note for the Web
version.</I></FONT><BR> First, as noted above, we've added
version 1.00 of the <TT>PalmComp</TT> package to the software
bundle for this column.  This version features the improvements
we suggested in our discussion of <TT>nextmatch()</TT> above.  We
replace <TT>nextmatch()</TT> with a new routine
<TT>bestmatch()</TT> that looks backwards for a string match to
the beginning of the buffer, finding the longest, closest one.
This newer version improves our compression by about 5%, and our
runtime by about 30%.  The details of the code are explained in
the internal comments.
<BR> <P> Second, after we submitted this article, the
<TT>Inline</TT> Perl package came to our attention.  This package
provides a way to drop C (or some other language) code directly
in-line in a Perl program, without wrapping it in an <TT>XS</TT>
file first.  For details see <TT><A
HREF="http://www.perl.com/pub/2001/02/inline.html">http://www.perl.com/pub/2001/02/inline.html</A></TT>

or the <TT>Inline</TT> package at CPAN, <TT><A
HREF="http://www.cpan.org/">http://www.cpan.org/</A></TT>.
</BODY></HTML>
<!--
palmcomp.mm:
     $Id: palmcomp.mm,v 1.7 2001/03/12 21:47:16 jeff Exp $
Mon Mar 12 13:47:50 PST 2001
-->
